package q53_maxSubArray;

public class Solution {
    public static void main(String[] args) {
        // int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        // int[] nums = {5,4,-1,7,8};
        int[] nums = {0,-3,1,1};
        Solution s = new  Solution();
        int a = s.maxSubArray(nums);
        System.out.println(a);
    }


    /**
     * 假设 nums 数组的长度是 n，下标从 0 到 n-1。
     * 用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」
     * 我们所需要的答案就是0 - (n - 1) 范围内的max f(i)
     * 所以只需要从0开始，找到每个位置的f(i), 最后得到最大值
     * 我们可以研究f(i) , f(i - 1) 和 nums[i] 的关系
     * 首先要了解的是，f(i)中所包含的一段并不一定包含了最后一个元素，可能是中间的一段子串
     *
     * 所以应该分开看，如果前面的f(i - 1)本身是一个小于0的数，意味着前面一段子串无论如何取，加上x这个位置都不会变大
     * 那么这个时候我们应该重新从x开始，找新的串，但如果前面的一段f(i - 1)是一个大于0的数，那么加上x后必然会使总值变大，
     * 这个时候就应该选择加上x得到f(i)
     *
     * 但是这样则需要不断记录f中哪个最大，最后才能得到答案
     */
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;

    }


    /**
     * 错误的解法
     * @param nums
     * @return
     */
//    public int maxSubArray(int[] nums) {
//        int res = 0;
//        int sum1 = 0,sum2 = 0;
//        int max1 = 0 ,max2 = nums.length - 1;
//        int bin1 = nums[0],bin2 = nums[nums.length - 1];
//        int de = nums[0];
//        for (int i = 0; i < nums.length; i++) {
//            sum1 += nums[i];
//            if (sum1 >= bin1){
//                max1 = i;
//                bin1 = sum1;
//            }
//            sum2 += nums[nums.length - 1 - i];
//            if (sum2 >= bin2){
//                max2 = nums.length - 1 - i;
//                bin2 = sum2;
//            }
//            de = Math.max(de,nums[i]);
//        }
//
//        System.out.println(max1);
//        System.out.println(max2);
//
//        if (max1 < max2) {
//            return de;
//        }
//        for (int i = max2; i <= max1; i++) {
//            res += nums[i];
//        }
//        return res;
//    }
}
